#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    """
    @param n: An integer
    @return: An integer
    """
    def numTrees(self, n):
        self.records = [-1] * (n+1)
        self.records[0] = 1     # 注意root == None, 只有一种二叉树
        # self.records[1] = 1     # 注意root == None, 只有一种二叉树

        # return self.rec_num(n)
        return self.rec_num_symmetric(n)

    def rec_num_symmetric(self, n):
        # 利用递归 + 对称性来计算
        if self.records[n] != -1:
            return self.records[n]

        if n == 1:
            return n

        half_idx = n // 2
        left_half_sum = 0
        mid_num = 0
        for root_idx in range(1, half_idx + 1):
            n1 = self.rec_num_symmetric(root_idx-1)
            n2 = self.rec_num_symmetric(n-root_idx)
            left_half_sum += n1 * n2       # NOTE: 注意这里是乘, 不是加

        if n % 2 == 1:
           mid_num = self.rec_num_symmetric(half_idx) ** 2     # 以中间元素为root, 左子树可能个数 * 右子树可能个数
        self.records[n] = left_half_sum * 2 + mid_num
        return self.records[n]

    # def rec_num(self, n):
    #     if self.records[n] != -1:
    #         return self.records[n]

    #     if n == 1:
    #         return n

    #     self.records[n] = 0
    #     for root_idx in range(1, n+1):
    #         n1 = self.rec_num(root_idx-1)
    #         n2 = self.rec_num(n-root_idx)
    #         sub = n1 * n2       # NOTE: 注意这里是乘, 不是加

    #         self.records[n] += sub

    #     # self.records[n] = sum
    #     return self.records[n]


def main():
    print("start main")
    s = Solution()
    ret = s.numTrees(1)
    # ret = s.numTrees(3)
    print(ret)

if __name__ == "__main__":
    main()
